//
// Created by Administrator on 2021/4/14.
//

/*
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个叶值序列 。



举个例子，如上图所示，给定一棵叶值序列为(6, 7, 4, 9, 8)的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是叶相似的。

如果给定的两个头结点分别为root1 和root2的树是叶相似的，则返回true；否则返回 false 。


示例 1：



输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true
示例 2：

输入：root1 = [1], root2 = [1]
输出：true
示例 3：

输入：root1 = [1], root2 = [2]
输出：false
示例 4：

输入：root1 = [1,2], root2 = [2,2]
输出：true
示例 5：



输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/leaf-similar-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;


struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

class Solution {
public:
    bool leafSimilar(TreeNode *root1, TreeNode *root2) {
        // 暴力： 得到两棵树的所有叶子序列，比较是否一致
        vector<int> v1;
        vector<int> v2;
        searchLeaf(root1, v1);
        searchLeaf(root2, v2);
        return v1 == v2;
    }

    // 搜索一棵树的所有叶节点
    void searchLeaf(TreeNode *root, vector<int> &v) {
        if (!root) return;
        // 加入叶节点
        if (root->left == nullptr and root->right == nullptr) {
            v.push_back(root->val);
            return; // 叶节点可以返回
        } else {
            searchLeaf(root->left, v);
            searchLeaf(root->right, v);
        }
    }

};


int main() {
    auto t3 = TreeNode(3);
    auto t2 = TreeNode(2);
    auto t1 = TreeNode(1, &t2, &t3);

    auto n3 = TreeNode(3);
    auto n2 = TreeNode(2);
    auto n1 = TreeNode(2, &n2, &n3);

    Solution sol;
    cout << (sol.leafSimilar(&t1, &n1) ? "true" : "false") << endl;


    return 0;
}